We shall attempt more particularly here below in this document to describe the issues and problems that exist in the field of elliptic curves and have been faced by the inventors of the present patent application. The invention naturally is not limited to this particular field of application but is of interest for all techniques using cryptographic parameters that have to cope with proximate or similar issues and problems.
Cryptosystems based on the use of elliptic curves have numerous advantages when compared with other asymmetrical cryptographic techniques such as RSA (Rivest Shamir Adleman), DSA (Digital Signature Algorithm) etc. More specifically, the cryptographic keys used in cryptosystems based on the use of elliptic curves have sizes (in numbers of bits) that are smaller than those used in the asymmetrical cryptographic techniques mentioned here above but provide equivalent or even greater security. In addition, the execution time for such cryptosystems based on elliptic curves is generally smaller than that of these other asymmetrical cryptographic techniques. This is why many standards-setting organizations promote the use of such cryptosystems. For example, the International Civil Aviation Organization (ICAO) which has standardized the electronic devices (in this case terminals) that have to read electronic documents (such as passports comprising electronic devices (a smart card for example), as well as, in a de facto manner, the document referenced “Doc 9303q stipulate the use of BAC (Basic Access Control) and PACE (Password Authenticated Connection Establishment) protocols which use operations on elliptic curves to secure exchanges between electronic devices (in this case between a terminal and a passport comprising a smart card). In addition, it must be noted that the SAC (Supplemental Access Control) protocol which is a more secured version of the BAC protocol and is itself also based on the use of elliptic curves, is tending to replace the BAC protocol. Here below, the generic term “electronic device” shall be used to denote a device that can be either such a terminal, or a smart card or any other equivalent device.
It must be noted that, before using an elliptic curve in a cryptosystem, an electronic device must necessarily ascertain that the parameters defining a curve comply with commonly accepted safety requirements. More specifically, it is generally necessary to implement validation algorithms that are described for example in paragraph 4 (Domain parameters) of the “Guide to Elliptic Curve Cryptography” by D. Hankerson et al (ISBN 0-387-95273-X). These algorithms thus ensure that the domain of parameters to be used does not have security flaws.
More specifically, the domain of the parameters, denoted as D, of an elliptic curve is defined by at most eight elements, D=(q, FR, S, a, b, P, n, h), where the number q makes it possible to define the q-element finite field, Fq, on which the elliptic curve is defined (i.e. q=pm, with m being an integer greater than or equal to 1, and p being a prime number greater than or equal to 2). The value of FR (for Field Representation) corresponds to an indication of the manner of representing an element belonging to the finite field Fq (for example where the field has the value 2 as its characteristic, this can be the irreducible m degree polynomial necessary to enable the representation of such elements). The numbers a and b are elements belonging to the q-element finite field. They correspond to coefficients enabling the definition of the equation of the elliptic curve considered, namely an equation of the type y2=x3+ax+b (when the characteristic of the field Fq is a prime number strictly greater than 2) or of an equation of the type y2+xy=x3+ax2+b (when the characteristic of the field Fq is equal to 2)). The value S corresponds to a seed which is a parameter that has been used to generate the elements a and b (thus, the value of S is not necessarily available for all the elliptic curves). The point P, which belongs to the elliptic curve (i.e. the affine coordinates of which verify the equation of the elliptic curve mentioned here above) and the order of which is the value of n which must be a prime number, can be given either as an affine coordinate or in another representation (a Jacobian representation, etc). Finally, the value h corresponds to that of the cofactor of the elliptic curve which must verify the following equality h=#E(Fq)/n where #E(Fq) corresponds to the number of points belonging to the elliptic curve considered.
The algorithm 4.15 (entitled “Explicit Domain parameter validation”) of the document “Guide to Elliptic Curve Cryptography” mentioned here above describes the different operations that have to be implemented by an electronic device so that it validates the field of parameters received.
It must be noted that the parameters FR and S do not always need to be transmitted. This does away with the need for carrying out certain steps of the algorithm identified. In particular, when a finite field Fp is used, it is not necessary to reference the parameter FR.
As mentioned here above, it is important to perform such a validation for reasons of security. For example, such a validation must be undertaken prior to the validation of a received public key as described in the patent application US20040114760, failing which the security of the exchanges linked to the use of such a public key would be impaired.
Thus, when an electronic device receives a domain of parameters associated with an elliptic curve, given the cumbersome nature (from the viewpoint of both memory space and of CPU (central processing unit) time), of the operations of the algorithm 4.15 mentioned here above, this device can be incapable of performing such operations. Thus, it becomes vitally important to find a solution to the problem of verifying a given domain of parameters.
Since there are numerous standards which, for certain curves, define domains of parameters for use (see for example the document “SEC 2: Recommended Elliptic Curve Domain Parameters” prepared by the firm Certicom Research, as well as the document “Finding cryptograpically Strong Elliptic Curves: A Technical Report I” by Hamish Ivey Law et al.) that ensure a high level of security, a first solution would be to store, for known and/or standardized curves (for example the curve whose identifier is “secp192k1” (also denoted as “elliptic Curve 31” in the document “SEC 2” mentioned here above), the domain of parameters of such curves. Thus, when an electronic device receives a domain of parameters, it must make a secured comparison between the parameters received and the parameters stored.
However, one drawback of such a technique lies in the fact that the electronic device must have substantial memory space to store, for each elliptic curve identifier, the corresponding domain of parameters. Such an approach necessitates the storage of all the parameters on the device. This can be a constraint when numerous curves have to be referenced.
A second solution would consist of the use of the technique described in the standards RFC 5915, RFC 5480 and RFC 5639. This is to send only the name of the curve or an identifier, also called universal identifiers or “curve OIDs” (curve object identifiers).
However, such a technique, which necessitates the storage of all the elements of a domain of parameters, has the same drawbacks as above from the viewpoint of management of the memory of the electronic device.
According to a third solution, the electronic device receives a domain of parameters as well as an identifier of the corresponding curve but this device stores only the identifier. However, such a technique does not guarantee that a valid identifier will be transmitted with a domain of parameters comprising the right parameters for the given curve. Thus, such a solution cannot be envisaged because it provides no guarantee (from a security viewpoint) on the elements received.
Finally, a fourth solution, which is generic (in that in the sense that it can be applied whatever the curve considered, whether or not it is known to the electronic device that receives a domain of parameters), would consist, from an algorithmic point of view, in optimizing the steps of the algorithm 4.15 to accelerate the verification of the elements of the domain of parameters (this time from an algorithmic point of view). However, no algorithmic improvement seems to have been achieved for the time being.
The present technique seeks to provide a solution to the problem of accelerating the verification of a given domain of parameters without the drawbacks of already existing solutions (i.e. a solution which, from the viewpoint of the electronic device, does not make it necessary to possess a large memory storage capacity while at the same time preserving its security).
Moreover, the domain of parameters of an elliptic curve is generally public. However, in a communications system, it can happen that such a domain is private (i.e. known only to the users of a communications system who are registered with the system). As a consequence, in this example, the verification of the domains of parameters has to be resistant to side-channel attacks.
The present technique is also aimed at providing a solution to such a problem. In addition, the present technique can be used to accelerate the validation of a domain of parameters for a hyperelliptic curve (see for example Fangguo Zhang et al “Compact Representation of Domain Parameters of Hyperelliptic Curve Cryptosystems” for a description of the operations to be performed to validate such a domain of parameters.